#ifndef DATA_STRUCTURE_ALGRAPH_H
#define DATA_STRUCTURE_ALGRAPH_H

#include "Graph.h"
#include "vector"
#include "queue"
#include <algorithm>

class ArcNode {//边节点
private:
    int vexIdx;
    ArcNode *node = nullptr;
    ArcType info;
public:
    ArcNode(int vexIdx, ArcType info) : vexIdx(vexIdx), info(info) {}

    int getVexIdx() const {
        return vexIdx;
    }

    void setVexIdx(int vexIdx) {
        ArcNode::vexIdx = vexIdx;
    }

    ArcNode *getNode() const {
        return node;
    }

    void setNode(ArcNode *node) {
        ArcNode::node = node;
    }

    ArcType getInfo() const {
        return info;
    }

    void setInfo(ArcType info) {
        ArcNode::info = info;
    }
};


class VNode {//点节点
private:
    verType data;
    ArcNode *firstArc = nullptr;
public:
    verType getData() const {
        return data;
    }

    void setData(verType data) {
        VNode::data = data;
    }

    ArcNode *getFirstArc() const {
        return firstArc;
    }

    void setFirstArc(ArcNode *arcNode) {
        if (this->firstArc != nullptr) {
            arcNode->setNode(firstArc);
        }
        firstArc = arcNode;
    }
};

class ListNode {
public:
    int idx;
    ListNode *next = nullptr;

    ListNode(int idx) : idx(idx) {}

    ListNode(int idx, ListNode *next) : idx(idx), next(next) {}
};

class ALGraph : public Graph {
private:
    VNode vertices[MVNum];

protected:
    verType findNode(int i) override {
        return vertices[i].getData();
    }

    void DFSS(int v1, int v2, bool visited[], string outStr, bool *ok) {
        outStr += vertices[v1].getData();
        if (v1 == v2) {
            cout << outStr;
            *ok = true;
        }
        outStr += "->";
        visited[v1] = true;
        for (ArcNode *w = vertices[v1].getFirstArc(); w != nullptr; w = w->getNode()) {
            if (!visited[w->getVexIdx()]) {
                DFSS(w->getVexIdx(), v2, visited, outStr, ok);
            }
        }
    }

public:
    ALGraph(int vexNum, int arcNum) : Graph(vexNum, arcNum) { this->create(); }

    void inputNode(int idx) override {
        verType data;
        cin >> data;
        vertices[idx].setData(data);
    }

    void inputArc() override {
        verType v1, v2;
        ArcType w;
        cin >> v1 >> v2 >> w;
        int i = findVexIdx(v1);
        int j = findVexIdx(v2);
        ArcNode *arcNode = new ArcNode(j, w);
        vertices[i].setFirstArc(arcNode);
    }

    void DFS(verType v1, verType v2) override {
        bool visited[vexNum];
        memset(visited, false, sizeof(visited));
        bool ok = false;
        DFSS(findVexIdx(v1), findVexIdx(v2), visited, "", &ok);
        if (!ok) {
            cout << "该两点没有联通路径" << endl;
        }
    }


    void BFS(verType v1, verType v2) override {
        bool visited[vexNum];
        memset(visited, false, sizeof(visited));
        queue<ListNode *> *queue = new std::queue<ListNode *>;
        int idx = findVexIdx(v1);
        int end = findVexIdx(v2);
        bool ok = false;

        queue->push(new ListNode(idx));
        visited[idx] = true;
        while (!queue->empty()) {
            ListNode *vi = queue->front();
            if (vi->idx == end) {
                cout << vertices[vi->idx].getData();
                vi = vi->next;
                for (; vi != nullptr; vi = vi->next) {
                    cout << "<-" << vertices[vi->idx].getData();
                }
                cout << endl;
                ok = true;
                break;
            }
            queue->pop();
            for (ArcNode *w = vertices[vi->idx].getFirstArc(); w != nullptr; w = w->getNode()) {
                if (!visited[w->getVexIdx()]) {
                    queue->push(new ListNode(w->getVexIdx(), vi));
                    visited[w->getVexIdx()] = true;
                }
            }
        }
        if (!ok) {
            cout << "该两点没有联通路径" << endl;
        }
    }
};


#endif //DATA_STRUCTURE_ALGRAPH_H
